/*
题目: 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

    例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

https://leetcode.cn/problems/restore-ip-addresses
 */
public class RestoreIpAddresses {
    List<String> result = new ArrayList<> ();
    // path 代表分组后的字符串
    List<String> path = new ArrayList<> ();
    int n = 0;

    //回溯 - 分割问题
    public List<String> restoreIpAddresses(String s) {
        n = s.length();
        if (n < 4 || n > 12)    return result;
        backTrack(s, 0);
        return result;
    }

    private void backTrack(String s, int start) {
        if (path.size() > 4) {  //分组数量超过四组
            return ;
        }
        //刚好分成四组 并且 刚好用完
        if (path.size() == 4 && start == n) {
            result.add(turnToResult());
            return ;
        }

        for (int i = start; i < n; i++) {
            if (isValid(s, start, i + 1)) { //如果有效
                path.add(s.substring(start, i + 1));
                backTrack(s, i + 1);
                path.remove(path.size() - 1);
            } else {
                break;
            }
        }
    }

    //将 path 的字符串连接成答案格式
    private String turnToResult() {
        int i = 0;
        String builder = "";
        while (i < path.size() - 1) {
            builder += path.get(i);
            builder += ".";
            i ++;
        }
        builder += path.get(i);
        return builder;
    }

    //判断这一段是否是有效的 IP 地址, 左闭右开
    private boolean isValid(String s, int start, int end) {
        int len = end - start;
        int sum = 0;
        if (s.charAt(start) == '0' && len > 1) return false; //含有前置0

        for (int i = start; i < end; i++) {
            sum = sum * 10 + s.charAt(i) - '0';
        }
        return sum <= 255;
    }
}
